#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define VEXSIZE 10
typedef char VertexType;
typedef int EdgeType;

// 定义邻接表中链表的结点（弧的另一个结点）
typedef struct ENode {
    EdgeType ivex;              // 弧的顶点下标（对应数组中的位置）
    struct ENode *next_edge;    // 指向下一个弧
}ENode, *PENode;

// 定义邻接表中各链表的顶点（图中结点的数据结构）
typedef struct VNode {
    VertexType data;            // 顶点的值
    ENode *first_edge;          // 指向依附于这个结点的第一个弧
}VNode, *PVNode;

// 定义图的数据结构
typedef struct {
    int vexnum, edgenum;
    VNode vex[VEXSIZE];
}LGraph;

/**
 * 获取指定元素在图中顶点的下标
 * 未查询到返回-1
 * @param pG
 * @param v
 * @return
 */
int get_position(LGraph pG, VertexType v) {
    for (int i = 0; i < pG.vexnum; ++i) {
        if (v == pG.vex[i].data) {
            return i;
        }
    }
    return -1;
}

/**
 * 邻接表中的链表尾部插入边顶点
 * @param EdgeLink
 * @param edgeVo
 */
void last_link(VNode &edgeVi, ENode *edgeVo) {
    if (edgeVi.first_edge == NULL) {
        edgeVi.first_edge = edgeVo;
    } else {
        ENode *p = edgeVi.first_edge;
        while (p->next_edge) {
            p = p->next_edge;
        }
        p->next_edge = edgeVo;
    }
}


/**
 * 图的邻接表 初始化
 * @param pG
 * @param vexs
 * @param edges
 * @return
 */
bool LGraph_Init(LGraph *&pG) {
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
            {'A', 'B'},
            {'B', 'C'},
            {'B', 'E'},
            {'B', 'F'},
            {'C', 'E'},
            {'D', 'C'},
            {'E', 'B'},
            {'E', 'D'},
            {'F', 'G'}};

    if ((pG = (LGraph*) malloc(sizeof (LGraph))) == NULL) {
        return false;
    }
    memset(pG, 0, sizeof (LGraph));

    int vexnum = sizeof (vexs) / sizeof (vexs[0]);
    int edgenum = sizeof (edges) / (sizeof (edges[0]));

    pG->vexnum = vexnum;
    pG->edgenum = edgenum;
    // 初始化图的顶点
    for (int i = 0; i < vexnum; ++i) {
        pG->vex[i].data = vexs[i];
        pG->vex[i].first_edge = NULL;
    }
    // 初始化图的边（有向图）
    for (int i = 0; i < edgenum; ++i) {
        VertexType vi = edges[i][0];
        VertexType vo = edges[i][1];
        int vi_index = get_position(*pG, vi);
        int vo_index = get_position(*pG, vo);

        ENode *edgeVo = (PENode) malloc(sizeof (ENode));
        edgeVo->ivex = vo_index;
        edgeVo->next_edge = NULL;
        // 有向图只需插入弧的终点即可（链表尾插法）
        last_link(pG->vex[vi_index], edgeVo);
    }
    return true;
}

/**
 * 打印当前顶点，并深度优先遍历该顶点
 */
void DFS(LGraph G, int index, int *visited) {
    printf("%2c", G.vex[index].data);
    visited[index] = 1;                 // 标记顶点被访问

    ENode *node = G.vex[index].first_edge;
    while(node != NULL) {
        if (visited[node->ivex] == 0) {
            DFS(G, node->ivex, visited);
        }
        node = node->next_edge;         // 深度优先遍历链表顺序靠前的顶点后，遍历该顶点连接的其他顶点
    }
}

/**
 * 图的深度优先遍历
 * 递归深度遍历每一个顶点
 * @param G
 */
void DFSTraverse(LGraph G) {
    int visited[VEXSIZE];               // 辅助数组，记录顶点是否被访问过
    // 辅助数组初始化
    for (int i = 0; i < G.vexnum; ++i) {
        visited[i] = 0;
    }
    // 遍历
    for (int i = 0; i < G.vexnum; ++i) {
        if (visited[i] == 0) {
            DFS(G, i, visited);
        }
    }
    printf("\n");
}

/**
 * 图的广度优先遍历
 * 依次出队访问辅助队列中的顶点，并将其子顶点入队
 * @param G
 */
void BFSTraverse(LGraph G) {
    int queue[VEXSIZE];                 // 辅助队列，记录广度遍历时待遍历的顶点
    int front = 0, rear = 0;            // 辅助队列头尾指针
    int visited[VEXSIZE];               // 辅助数组，记录顶点是否被访问过

    // 辅助数组初始化
    for (int i = 0; i < G.vexnum; ++i) {
        visited[i] = 0;
    }

    // 依次遍历
    for (int i = 0; i < G.vexnum; ++i) {
        // 如果顶点未访问，则访问该顶点并将其入队
        if (visited[i] == 0) {
            printf("%2c", G.vex[i].data);
            visited[i] = 1;
            queue[rear++] = i;
        }
        // 如果队列不为空，则访问队头元素
        while (front != rear) {
            int index = queue[front++]; // 获得队头顶点并使其出队
            ENode *node = G.vex[index].first_edge;
            // 将该顶点关联的其他顶点依次访问并入队
            while (node != NULL) {
                int next_index = node->ivex;
                if (visited[next_index] == 0) {
                    printf("%2c", G.vex[next_index].data);
                    visited[next_index] = 1;
                    queue[rear++] = next_index;
                }
                node = node->next_edge;
            }
        }
    }
    printf("\n");
}

/**
 * 图的顶点和边如下，直接初始化好，无需读取标准输入，完成有向图的邻接表初始化，完成深度优先遍历，广度优先遍历
 *
 *      char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
 *      char edges[][2] = {
 *      {'A', 'B'},
 *      {'B', 'C'},
 *      {'B', 'E'},
 *      {'B', 'F'},
 *      {'C', 'E'},
 *      {'D', 'C'},
 *      {'E', 'B'},
 *      {'E', 'D'},
 *      {'F', 'G'}};
 *
 * @return
 */
int main() {

    // 有向图的邻接表初始化
    LGraph *pG;
    LGraph_Init(pG);

    // 图的深度优先遍历
    DFSTraverse(*pG);

    // 图的广度优先遍历
    BFSTraverse(*pG);

    return 0;
}